<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>二叉搜索树</title>
</head>
<body>
<script>
    //封装二叉搜索树
    function BinarySearchTree() {

        function Node(key) {
            this.key = key;
            this.left = null;
            this.right = null;
        }

        /*属性*/
        this.root = null;//根节点

        /*方法*/
        //添加节点方法
        BinarySearchTree.prototype.insert = function (key) {
            //1.根据Key创建节点
            let newNode = new Node(key);

            //2.判断根节点是否有值
            if(this.root == null) {
                this.root = newNode;
            }else {
                this.insertNode(this.root, newNode);
            }
        };
        BinarySearchTree.prototype.insertNode = function (node, newNode) {
            if(newNode.key < node.key) { //向左查找
                if(node.left == null) { //表示没有左子节点
                    node.left = newNode;
                }else {
                    this.insertNode(node.left, newNode);
                }
            }else if (newNode.key > node.key) {
                if(node.right == null) {
                    node.right = newNode;
                }else {
                    this.insertNode(node.right, newNode);
                }
            }
        };

        //先序遍历
        BinarySearchTree.prototype.preOrderTraversal = function (handle) {
            this.preOrderTraversalNode(this.root, handle);
        };
        BinarySearchTree.prototype.preOrderTraversalNode = function (node, handle) {
            if(node != null) { //节点不为空
                handle(node.key);
                this.preOrderTraversalNode(node.left, handle);
                this.preOrderTraversalNode(node.right, handle);
            }
        };

        //中序遍历
        BinarySearchTree.prototype.midOrderTraversal = function (handle) {
            this.midOrderTraversalNode(this.root, handle);
        };
        BinarySearchTree.prototype.midOrderTraversalNode = function (node, handle) {
            if(node != null) {
                this.midOrderTraversalNode(node.left, handle);
                handle(node.key);
                this.midOrderTraversalNode(node.right, handle);
            }
        };

        //后序遍历
        BinarySearchTree.prototype.postorderOrderTraversal = function (handle) {
            this.postorderOrderTraversalNode(this.root, handle);
        };
        BinarySearchTree.prototype.postorderOrderTraversalNode = function (node, handle) {
            if(node != null) {
                this.postorderOrderTraversalNode(node.left, handle);
                this.postorderOrderTraversalNode(node.right, handle);
                handle(node.key);
            }
        };

        //获取最大值
        BinarySearchTree.prototype.getMax = function () {
            let node = this.root;
            let key = null;
            while (node != null) {
                key = node.key;
                node = node.right;
            }
            return null;
        };

        //获取最小值
        BinarySearchTree.prototype.getMin = function () {
            let node = this.root;
            let key = null;
            while (node != null) {
                key = node.key;
                node = node.right;
            }
            return key;
        };

        //搜索某一个key是否存在
        BinarySearchTree.prototype.search = function (key) {
            let node = this.root;
            while (node != null) {
                if (key < node.key) {
                    node = node.left;
                } else if (key > node.key) {
                    node = node.right;
                } else {
                    return true
                }
            }
            return false;
        }

        //删除一个节点
        BinarySearchTree.prototype.remove = function (key) {
            // 1.寻找要删除的节点
            // 1.1定义变量，保存一些信息
            let current = this.root; //指向要删除的节点
            if (current === null) {return false}
            let parent = null;  //指向要删除的节点的父节点
            let isLeftChild = true; //判断要删除的节点是在父节点的左边还是右边

            // 1.2开始寻找要删除的节点
            while (current.key !== key) {
                parent = current;
                if (key < current.key) {
                    isLeftChild  = true;
                    current = current.left
                } else {
                    isLeftChild = false;
                    current = current.right;
                }

                //说明没有找到，返回false
                if (current === null) {return false}
            }

            // 2.根据对应的情况删除节点
            // 2.1删除的节点是叶子节点
            if (current.left === null && null === current.right) { //写成current.left === null === current.right 不会有断路效果
                if (current === this.root) { //只有一个根节点的情况
                    this.root = null
                } else if (isLeftChild) { //要删除的叶节点在左边
                    parent.left = null;
                } else { //要删除的叶节点在右边
                    parent.right = null;
                }
            }

            // 2.2删除的节点有一个子节点
            else if (current.right === null) { //2.2.1 删除的节点的子节点在左边
                if (current === this.root) { //要删除的节点是根节点
                    this.root = current.left;
                } else if (isLeftChild) { //删除的节点在父节点的左边
                    parent.left = current.left
                } else {
                    parent.right = current.left
                }
            } else if (current.left === null) { //2.2.2 删除的节点的子节点在右边
                if (current === this.root) {
                    this.root = current.right;
                } else if (isLeftChild) { //删除的节点在父节点的左边
                    parent.left = current.right
                } else {
                    parent.right = current.right
                }
            }

            // 2.3删除的节点有两个节点,节点被删除后需要用被删除节点的后继代替其位置
            else {
                let successor = getSuccessor(current); //先拿到被删除节点的后继
                /**
                 * 上面这个successor节点的right已经指向被删除节点的right,其left也已经指向被删除节点的left。
                 * 在getSuccessor()函数里完成这些操作。
                 * 所有接下来只要将被删除的父节点right/left指向successor (后继节点)
                 * 如果被删除节点在被删除节点的父节点的左边，则被删除的父节点left指向successor,
                 * 被删除节点在被删除节点的父节点的右边，则被删除的父节点right指向successor。
                 */

                // 2.3.1 判断被删除节点的三种不同情况
                if (current === this.root) { //删除的节点是根节点
                    this.root = successor
                } else if (isLeftChild) { //被删除的节点在父节点的左边，则将父节点left指向successor(被删除节点的后继)，然后需删除的节点则没有被其它节点所指向 则会被在内存中释放(被删除)
                    parent.left = successor
                } else {// 被删除的节点在父节点的右边
                    parent.right = successor
                }


            }

        };
        
        //找后继的方法
        function getSuccessor(delNode) {
            let successor = delNode; //指向需要删除节点的后继
            let current = delNode.right;//先指向右边第一个节点，准备向右边开始找
            let successParent = delNode; //指向需要删除节点的后继的父节点

            //循环查找
            while (current !== null) {
                successParent = successor;
                successor = current;
                current = current.left;
            }

            //判断后继节点是否就是delNode的right节点
            if (successor !== delNode.right) { //如果不是
                successParent.left = successor.right; //后继节点的父节点指向后继节点的right
                successor.right = delNode.right; //后继节点right指向被删除节点的right,后继节点顶替被删除节点的操作之一
            }
            successor.left = delNode.left; //后继节点left指向被删除节点的left,后继节点顶替被删除节点的操作之一

            return successor
        }

    }

    let b = new BinarySearchTree();
    b.insert(11);
    b.insert(7);
    b.insert(15);
    b.insert(5);
    b.insert(3);
    b.insert(9);
    b.insert(8);
    b.insert(10);
    b.insert(13);
    b.insert(12);
    b.insert(14);
    b.insert(20);
    b.insert(18);
    b.insert(25);
    b.insert(6);

    let result = "";
    b.preOrderTraversal(function (key) {
        result += key + " ";
    });
    let result2 = "";
    b.midOrderTraversal(function (key) {
        result2 += key + " ";
    });
    let result3 = "";
    b.postorderOrderTraversal(function (key) {
        result3 += key + " ";
    });
    console.log("先序遍历"+result);
    console.log("中序遍历"+result2);
    console.log("后序遍历"+result3);
</script>
</body>
</html>